// 给定一个m * n大小的二维字符矩阵board和一个字符串单词word，如果word存在于网格中，返回true，否则返回false
// 单词必须按照字母顺序通过上下左右相邻的单元格字母构成，且同一个单元格内的字母不允许被重复使用
// 思路，回溯
// 回溯算法在二维矩阵中按照上下左右四个方向递归搜索，设函数backtrack(i, j, index)表示从board[i][j]出发，能否搜索到单词字母word[index]
// 以及index位置之后的后缀子串，如果能搜索到返回true，否则返回false, backtrack(i, j, index)执行步骤如下：
// 1. 如果board[i][j] === word[index], 而且index已经到达了word字符串末尾，返回true
// 2. 如果board[i][j] === word[index], 而且index未到达word字符串末尾，遍历当前位置的所有相邻位置，如果从某个相邻位置能搜索到后缀子串，则返回true，否则返回false
// 3. 如果board[i][j] !== word[index], 则当前字符不匹配，返回false

function exist(board, word) {
    let directs = [[0 ,1], [0, -1], [1, 0], [-1, 0]]
    let rows = board.length
    if (board.length === 0) {
        return false
    }
    let cols = board[0].length
    // 这里注意别构造错了
    let visited = new Array(rows).fill(0).map(_ => new Array(cols).fill(false))
    
    function backtracking(i, j, index) {
        if (index === word.length - 1) {
            return board[i][j] === word[index]
        }
        if (board[i][j] === word[index]) {
            visited[i][j] = true
            for (let k = 0; k < directs.length; k++) {
                let newI = i + directs[k][0]
                let newJ = j + directs[k][1]
                if (newI >= 0 && newI < rows && newJ >= 0 && newJ < board[0].length && visited[newI][newJ] === false) {
                    if (backtracking(newI, newJ, index + 1)) {
                        return true
                    }
                }
            }
            visited[i][j] = false
        }
        return false
    }
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < board[0].length; j++) {
            if (backtracking(i, j, 0)) {
                return true
            }
        }        
    }
    return false
}

let board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
console.log(exist(board, word))